Non-volatile storage devices (NVS), such as flash memory, may be used for the storage of data in computing system applications. There are currently two types of flash memory in general use, with other types being developed. NOR flash and NAND flash have differing write and read speeds, differing lifetimes, and costs. NAND flash is preferred at present for large memory systems. The architecture of a NAND flash memory system is influenced, in part, by the desire to replace rotating media (e.g., magnetic disks) or tape as a bulk storage device. A characteristic of a flash memory device is that the organization of the memory locations may emulate a sector, page, and volume of a disk. However, there are certain differences in the implementing technology which need to be accommodated. In particular, whereas a disk sector may be written to multiple times in succession, a sector of flash memory may be written to once. Prior to another write operation, the sector must be erased. However, the minimum size of the memory area that may be erased may be large when compared with a sector or a page. This minimum sized area of physical memory that is erasable is termed a “block”, and is a plurality of contiguous pages which may have a definite relationship to the chip electrical construction.
To perform an elemental write operation on a previously unwritten page, the page of data may be written to directly to the memory area. This is sometimes called programming, and selectively sets bits of the page to “0” from the previous “1” state so as to record the data. When the data in the page location needs to be modified, the modification cannot be performed in place, unless all of the bits of the page are first set all to “1” again, which is an operation termed “erase”. But erase operations cannot be performed on a territory area smaller than a block, which may be, for example 128 pages. So, in order to write one byte, the memory controller may have to read 128 pages, erase the block, and write all of the data, including the modified byte, back to the memory area. This is inefficient. As well, the number of erase operations is high, and one aspect of flash product lifetime is the number of erase operations which may be performed prior to device wear out.
A more efficient approach is to read the page to be modified (a “live” or “active” page, containing valid current data) make the data modification in local volatile memory, and write the modified page data to a free page. A “free” page is one which has never been programmed, or has been erased as part of a block erase operation. After the write operation, the free page becomes an active page, and the page that has been read from is now out-of-date, and is called a “dead” page, or a “stale” page.
Another limitation of currently used NAND flash is that the pages of a block need are written in sequential order beginning with the first page, so as to minimize write-disturb errors. Any blocks not written to in this order would remain free until the block is again erased. As this wastes storage space, the usual policy is to write to each page of a block in sequential order, although the writing need not be time continuous. Data at the original location of the page being modified is left in place in the memory, as pages cannot be individually erased. So, a dead or stale page of memory is out-of-date, and not longer of use, but still occupied memory space. Eventually, the memory would become filled with a combination of active and dead pages, and all of the free pages would be exhausted.